import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        System.out.println("Hello world!");
    }
}

class Solution {
    List<Integer> cur = new ArrayList<>(9);
    int curSum = 0;
    List<List<Integer>> ans = new ArrayList<>();

    public List<List<Integer>> combinationSum3(int k, int n) {
        backtracking(k, n, 1);
        return ans;
    }

    void backtracking(int k, int n, int i) {
        //列表无法达到长度k剪枝
        if (cur.size() + 9 - i + 1 < k || cur.size() > k) {
            return;
        }

        //合法解
        if (cur.size() == k && curSum == n) {
            ans.add(new ArrayList<>(cur));
            return;
        }

        //和无法达到n或已经超过n剪枝
        if (curSum + i > n || curSum + (i + 9) * (9 - i + 1) / 2 < n) {
            return;
        }

        //回溯
        if (i > 9) {
            return;
        }
        backtracking(k, n, i + 1);
        cur.add(i);
        curSum += i;
        backtracking(k, n, i + 1);
        curSum -= i;
        cur.remove(cur.size() - 1);
    }
}